-- N皇后问题求解器
local function solveNQueens(n)
    local solutions = {}
    local queens = {}
    for i = 1, n do
        queens[i] = -1
    end
    local columns = {}
    local diagonal1 = {}
    local diagonal2 = {}
    local row = {}
    for i = 1, n do
        row[i] = "."
    end
    
    -- 生成棋盘字符串表示
    local function generateBoard()
        local board = {}
        for i = 1, n do
            local temp = {}
            for j = 1, n do
                if j == queens[i] + 1 then
                    temp[j] = "Q"
                else
                    temp[j] = "."
                end
            end
            board[i] = table.concat(temp)
        end
        return board
    end
    
    -- 回溯函数
    local function backtrack(row_idx)
        if row_idx == n + 1 then
            local board = generateBoard()
            table.insert(solutions, board)
        else
            for i = 1, n do
                local col = i - 1
                local diag1 = row_idx - col
                local diag2 = row_idx + col
                
                -- 检查列和对角线是否冲突
                local conflict = false
                for k, v in pairs(columns) do
                    if v == col then
                        conflict = true
                        break
                    end
                end
                if not conflict then
                    for k, v in pairs(diagonal1) do
                        if v == diag1 then
                            conflict = true
                            break
                        end
                    end
                end
                if not conflict then
                    for k, v in pairs(diagonal2) do
                        if v == diag2 then
                            conflict = true
                            break
                        end
                    end
                end
                
                if not conflict then
                    queens[row_idx] = col
                    table.insert(columns, col)
                    table.insert(diagonal1, diag1)
                    table.insert(diagonal2, diag2)
                    backtrack(row_idx + 1)
                    
                    -- 回溯操作
                    for k, v in ipairs(columns) do
                        if v == col then
                            table.remove(columns, k)
                            break
                        end
                    end
                    for k, v in ipairs(diagonal1) do
                        if v == diag1 then
                            table.remove(diagonal1, k)
                            break
                        end
                    end
                    for k, v in ipairs(diagonal2) do
                        if v == diag2 then
                            table.remove(diagonal2, k)
                            break
                        end
                    end
                end
            end
        end
    end
    
    backtrack(1)
    return solutions
end

-- 测试代码
local startTime = os.clock()
local solutionsArray = {}
for i = 0, 14 do
    local solutionsText = solveNQueens(i)
    solutionsArray[i+1] = #solutionsText
end
print(solutionsArray[#solutionsArray])
print(os.clock() - startTime)